<!DOCTYPE html>
<html lang="en"><head>
    <title>CZH-DEV BLOG</title>
    <meta content="text/html;charset=utf-8" http-equiv="Content-Type">
    <meta content="utf-8" http-equiv="encoding">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <meta name="format-detection" content="telephone=no" />
    <meta name="theme-color" content="#000084" />
    <link rel="icon" href="https://czh-dev.gitee.io/czh-blog.gitee.io//favicon.ico">
    <link rel="canonical" href="https://czh-dev.gitee.io/czh-blog.gitee.io/">
    
    
</head>
<body>
<nav class="navbar navbar-inverse navbar-fixed-top">
    <div class="navbar-inner">
        <div class="container">
            <button type="button" class="btn btn-navbar" data-toggle="collapse" data-target=".nav-collapse"></button>
            <a class="brand" href="https://czh-dev.gitee.io/czh-blog.gitee.io/">CZH-DEV BLOG</a>
            <div class="nav-collapse collapse">
                <ul class="nav">
                    
                    
                        
                            <li>
                                <a href="/czh-blog.gitee.io/about/">
                                    
                                    <span>About</span>
                                </a>
                            </li>
                        
                    
                        
                            <li>
                                <a href="/czh-blog.gitee.io/post/">
                                    
                                    <span>All posts</span>
                                </a>
                            </li>
                        
                    
                        
                            <li>
                                <a href="/czh-blog.gitee.io/ebook/">
                                    
                                    <span>Resource</span>
                                </a>
                            </li>
                        
                    
                </ul>
            </div>
        </div>
    </div>
</nav><div id="content" class="container">
<div style="display: flex;">
  <div class="row-fluid navmargin">
    <div class="page-header">
      <h1>HashMap深入剖析 - Sat, Feb 18, 2023</h1>
    </div>
    <p class="lead"></p>
    <h1 id="hashmap源码剖析">HashMap源码剖析</h1>
<h2 id="面试题">面试题</h2>
<h3 id="谈一下hashmap中put是如何实现的"><strong>谈一下hashMap中put是如何实现的？</strong></h3>
<ol>
<li>先判断是不是第一次put元素,如果是,就先初始化hashmap,负载因子0.75, 默认容量16 ,扩容阈值16*0.75=12</li>
<li>如果索引位置为null,就把新元素放入到索引位置</li>
<li>如果索引位置不为null, 判断新旧元素的地址或者key是否相同,是否是一个元素,如果是,就把新元素的value替换旧元素的value</li>
<li>如果索引位置的元素类型是treeNode,就进行红黑树操作</li>
<li>如果索引位置的元素是链表,就在元素尾部增加新的节点,</li>
<li>如果增加的节点数量操作8个,,并且数组的长度小于64,进行扩容.</li>
<li>否则,进行链表转红黑树的操作, 先把单向链表转换为双向链表,在转换为红黑树.</li>
</ol>
<h3 id="为什么重写equals必须重写hashcode方法"><strong>为什么重写equals,必须重写hashCode方法?</strong></h3>
<p>如果不重写,hashcode是依据内存地址存放元素的. 不写hashCode ,代码不稳定.如果:</p>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4;"><code class="language-java" data-lang="java"><span style="display:flex;"><span>Persion p1<span style="color:#f92672">=</span><span style="color:#66d9ef">new</span> Persion<span style="color:#f92672">(</span>18<span style="color:#f92672">,</span><span style="color:#e6db74">&#34;czh&#34;</span><span style="color:#f92672">);</span> <span style="color:#75715e">//  hash   18     index 2
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>Persion p2<span style="color:#f92672">=</span><span style="color:#66d9ef">new</span> Persion<span style="color:#f92672">(</span>18<span style="color:#f92672">,</span><span style="color:#e6db74">&#34;czh&#34;</span><span style="color:#f92672">);</span> <span style="color:#75715e">// hash    19    index 3
</span></span></span></code></pre></div><p>相同对象,存放的位置不是一个索引.也可能一个索引存放不同的对象.
如果</p>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4;"><code class="language-java" data-lang="java"><span style="display:flex;"><span>Persion p1<span style="color:#f92672">=</span><span style="color:#66d9ef">new</span> Persion<span style="color:#f92672">(</span>18<span style="color:#f92672">,</span><span style="color:#e6db74">&#34;czh&#34;</span><span style="color:#f92672">);</span> <span style="color:#75715e">//  hash   18     index 2
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>Persion p2<span style="color:#f92672">=</span><span style="color:#66d9ef">new</span> Persion<span style="color:#f92672">(***,</span><span style="color:#e6db74">&#34;czh&#34;</span><span style="color:#f92672">);</span> <span style="color:#75715e">// hash    18    index 2
</span></span></span></code></pre></div><p>size 大小, 可能等于1 也可能等于2</p>
<h3 id="谈一下hashmap中什么时候需要进行扩容扩容resize又是如何实现的"><strong>谈一下hashMap中什么时候需要进行扩容，扩容resize()又是如何实现的？</strong></h3>
<p>扩容条件:
1. -map元素大于扩容的阈值
2. -链表长度大于8并且数组长度小于64的情况下会扩容</p>
<p>扩容实现:</p>
<ol>
<li>遍历所有旧数组</li>
<li>旧数组索引位置如果为null ,啥也不做</li>
<li>旧数组索引位置如果只有一个元素,重新计算hash值,把这个元素放入到新数组,相应索引的位置</li>
<li>旧数组索引位置是treeNode类型,就做红黑树的分割操作,红黑树也会分为低位树和高位树,如果树的节点数量低于6个,红黑树会转变为单向链表</li>
<li>旧数组索引位置是单向链表,把单向链表按照高位和低位重新建立两个链表,把首元素放入到对应的索引位置.,</li>
</ol>
<h3 id="为什么不直接将key作为哈希值而是与高16位做异或运算"><strong>为什么不直接将key作为哈希值而是与高16位做异或运算？</strong></h3>
<p>扰动一下,让所有的数据都参与到hashcode的计算中来,让hashcode分布更加均匀</p>
<h3 id="为什么是16为什么必须是2的幂如果输入值不是2的幂比如10会怎么样"><strong>为什么是16？为什么必须是2的幂？如果输入值不是2的幂比如10会怎么样？</strong></h3>
<ol>
<li>在hashMap中,会通过tableSizeFor方法,找到一个大于初始容量的2的倍数作为table容量.</li>
<li>如果不这么处理,数据分布会不均匀,出现漏位现象. 如果输入的是10 ,那么1.3.5.,,,, 奇数位永远不会被使用.</li>
<li>并且,使用2的幂次,可以用x&amp;(n-1) 代替取模操作.提高效率</li>
</ol>
<h3 id="谈一下当两个对象的hashcode相等时会怎么样"><strong>谈一下当两个对象的hashCode相等时会怎么样？</strong></h3>
<p>hashcode相同时,就是Hash碰撞.碰撞的hash 会存储在同一个桶位置. 如果数组小于64,链表小于等于8的长度,会使用单向链表结构,否则,使用红黑树结构.</p>
<h3 id="如果两个键的hashcode相同你如何获取值对象"><strong>如果两个键的hashcode相同，你如何获取值对象？</strong></h3>
<ol>
<li>先判断索引处的元素与要获取的元素是不是一个元素,如果是,就返回这个对象</li>
<li>如果不是,判断索引处的元素的next是否为null</li>
<li>如果不为null,判断是否为treeNode,如果是就进行红黑树的查找</li>
<li>如果不是treeNode,那么就是链表,循环链表查找元素,返回元素.</li>
</ol>
<h3 id="如果hashmap的大小超过了负载因子load-factor定义的容量怎么办"><strong>如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？</strong></h3>
<p>如果数组长度小于64,会触发扩容操作,超过64,会触发链表转换为红黑树的操作.</p>
<h3 id="请解释一下hashmap的参数loadfactor它的作用是什么"><strong>请解释一下HashMap的参数loadFactor，它的作用是什么？</strong></h3>
<p>loadFactor 是负载因子,表示节点数/hash表桶数,表示hashmap的拥挤程度.默认是0.75.</p>
<h3 id="传统hashmap的缺点为什么引入红黑树"><strong>传统HashMap的缺点(为什么引入红黑树？)：</strong></h3>
<p>红黑树的访问路径要短于双向链表. 效率比较高. 空间换时间.
单向链表的时间复杂度为O(n),而红黑树的时间复杂度O(logN),索引红黑树的效率更高一些.</p>
<h2 id="存储需求">存储需求</h2>
<blockquote>
<p>设计一个写字楼通讯录，存放所有公司的通讯信息
座机号码作为 key（假设座机号码最长是 8 位），公司详情（名称、地址等）作为 value
添加、删除、搜索的时间复杂度要求是 O(1)</p>
</blockquote>
<ul>
<li>
<p>代码实现：</p>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4;"><code class="language-java" data-lang="java"><span style="display:flex;"><span><span style="color:#66d9ef">public</span> <span style="color:#66d9ef">class</span> <span style="color:#a6e22e">PhoneList</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>    <span style="color:#66d9ef">private</span> Commpany<span style="color:#f92672">[]</span> commpanies <span style="color:#f92672">=</span> <span style="color:#66d9ef">new</span> Commpany<span style="color:#f92672">[</span>10000000<span style="color:#f92672">];</span>
</span></span><span style="display:flex;"><span>    <span style="color:#66d9ef">public</span> <span style="color:#66d9ef">void</span> <span style="color:#a6e22e">add</span><span style="color:#f92672">(</span><span style="color:#66d9ef">int</span> phone<span style="color:#f92672">,</span>Commpany commpany<span style="color:#f92672">){</span>
</span></span><span style="display:flex;"><span>        commpanies<span style="color:#f92672">[</span>phone<span style="color:#f92672">]</span> <span style="color:#f92672">=</span> commpany<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>    <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>    <span style="color:#66d9ef">public</span> <span style="color:#66d9ef">void</span> <span style="color:#a6e22e">remove</span><span style="color:#f92672">(</span><span style="color:#66d9ef">int</span> phone<span style="color:#f92672">){</span>
</span></span><span style="display:flex;"><span>        commpanies<span style="color:#f92672">[</span>phone<span style="color:#f92672">]</span> <span style="color:#f92672">=</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>    <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>    <span style="color:#66d9ef">public</span> Commpany <span style="color:#a6e22e">get</span><span style="color:#f92672">(</span><span style="color:#66d9ef">int</span> phone<span style="color:#f92672">){</span>
</span></span><span style="display:flex;"><span>        <span style="color:#66d9ef">return</span> commpanies<span style="color:#f92672">[</span>phone<span style="color:#f92672">];</span>
</span></span><span style="display:flex;"><span>    <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span><span style="color:#f92672">}</span>
</span></span></code></pre></div></li>
<li>
<p>存在问题：</p>
<ol>
<li>空间复杂度非常大</li>
<li>空间使用率极低,非常浪费内存空间</li>
</ol>
</li>
</ul>
<h2 id="哈希表hash-table">哈希表（Hash Table）</h2>
<p>哈希表也叫做散列表（ hash 有“剁碎”的意思）
它是如何实现高效处理数据的？</p>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4;"><code class="language-java" data-lang="java"><span style="display:flex;"><span>put<span style="color:#f92672">(</span><span style="color:#e6db74">&#34;jack&#34;</span><span style="color:#f92672">,</span>666<span style="color:#f92672">);</span>
</span></span><span style="display:flex;"><span>put<span style="color:#f92672">(</span><span style="color:#e6db74">&#34;Rose&#34;</span><span style="color:#f92672">,</span>777<span style="color:#f92672">);</span>
</span></span><span style="display:flex;"><span>put<span style="color:#f92672">(</span><span style="color:#e6db74">&#34;Kate&#34;</span><span style="color:#f92672">,</span>888<span style="color:#f92672">);</span>
</span></span></code></pre></div><h3 id="哈希冲突">哈希冲突</h3>
<p>哈希冲突也叫做哈希碰撞
2个不同的key,经过哈希函数计算出相同的结果
key1≠key2，hash(key1)=hash(key2)</p>
<h3 id="jdk18的哈希冲突解决方案">JDK1.8的哈希冲突解决方案</h3>
<ul>
<li>
<p>默认使用单向链表将元素串起来</p>
</li>
<li>
<p>在添加元素是,可能会由单向链表转成红黑树来存储元素
比如当哈希表容量&gt;=64且单向链表的节点数量大于8时</p>
</li>
<li>
<p>当红黑树节点数量少到一定程度时(6个)，又会转成单向链表</p>
</li>
<li>
<p>JDK1.8中的哈希表是使用数组+链表+红黑树解决哈希冲突</p>
</li>
</ul>
<h3 id="哈希函数">哈希函数</h3>
<ol>
<li>
<p>先生成 key 的哈希值（必须是整数）</p>
</li>
<li>
<p>再让key的哈希值跟数组的大小进行相关运算，生成一个索引值</p>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4;"><code class="language-java" data-lang="java"><span style="display:flex;"><span><span style="color:#66d9ef">public</span> <span style="color:#66d9ef">int</span> <span style="color:#a6e22e">hash</span><span style="color:#f92672">(</span>Object key<span style="color:#f92672">){</span>
</span></span><span style="display:flex;"><span>     <span style="color:#66d9ef">return</span> hash_code<span style="color:#f92672">(</span>key<span style="color:#f92672">)</span> <span style="color:#f92672">%</span> table<span style="color:#f92672">.</span><span style="color:#a6e22e">length</span><span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span><span style="color:#f92672">}</span>
</span></span></code></pre></div></li>
<li>
<p>为了提高效率，可以使用&amp;位运算取代%运算【前提：将数组的长度设计为2的幂】</p>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4;"><code class="language-java" data-lang="java"><span style="display:flex;"><span><span style="color:#66d9ef">public</span> <span style="color:#66d9ef">int</span> <span style="color:#a6e22e">hash</span><span style="color:#f92672">(</span>Object key<span style="color:#f92672">){</span>
</span></span><span style="display:flex;"><span>      <span style="color:#66d9ef">return</span> hash_code<span style="color:#f92672">(</span>key<span style="color:#f92672">)</span> <span style="color:#f92672">&amp;</span> <span style="color:#f92672">(</span>table<span style="color:#f92672">.</span><span style="color:#a6e22e">length</span><span style="color:#f92672">-</span>1<span style="color:#f92672">);</span>
</span></span><span style="display:flex;"><span><span style="color:#f92672">}</span>
</span></span></code></pre></div></li>
<li>
<p>良好的哈希函数哈希值更加均匀分布&ndash;&gt;减少哈希冲突次数&ndash;&gt;提高哈希表性能</p>
</li>
</ol>
<h4 id="为什么容量大小需要是2的幂">为什么容量大小需要是2的幂？</h4>
<p>如果设计成10的情况下,数组的有些位置是无法使用到的,分布就不均匀,这样哈希冲突的次数就增加了,性能就受到影响了
计算机遇到取模计算时,改为位运算+加减法
如:
hash%16 &ndash;&gt; [0,15]
hash&amp;(16-1)
两个公式只有在2的幂次运算时,才相同. 也就是&amp;上任何数,取值范围都是0~这个数-1之间. 相当于取模操作.
1234 5678 9876 4321 &amp; 0000 0000 0000 1111 = 4321</p>
<h3 id="如何生成key的哈希值">如何生成key的哈希值</h3>
<p>key 的常见种类可能有 整数、浮点数、字符串、自定义对象
不同种类的 key，哈希值的生成方式不一样,但目标是一致的.</p>
<ol>
<li>尽量让每个key的哈希值是唯一的</li>
<li>尽量让key的所有信息参与运算</li>
</ol>
<p>在Java中，HashMap的key必须实现hashCode和equals方法</p>
<h4 id="int类型">int类型</h4>
<p>整数值当做哈希值
比如10的哈希值就是10</p>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4;"><code class="language-java" data-lang="java"><span style="display:flex;"><span><span style="color:#66d9ef">public</span> <span style="color:#66d9ef">static</span> <span style="color:#66d9ef">int</span> <span style="color:#a6e22e">hashCode</span><span style="color:#f92672">(</span><span style="color:#66d9ef">int</span> value<span style="color:#f92672">){</span>
</span></span><span style="display:flex;"><span>	<span style="color:#66d9ef">return</span> value<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span><span style="color:#f92672">}</span>
</span></span></code></pre></div><h4 id="浮点数类型">浮点数类型</h4>
<p>将存储的二进制格式转成整数值</p>
<h4 id="long和double类型">Long和Double类型</h4>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4;"><code class="language-java" data-lang="java"><span style="display:flex;"><span><span style="color:#66d9ef">public</span> <span style="color:#66d9ef">static</span> <span style="color:#66d9ef">int</span> <span style="color:#a6e22e">hashCode</span><span style="color:#f92672">(</span><span style="color:#66d9ef">long</span> value<span style="color:#f92672">){</span>
</span></span><span style="display:flex;"><span>     <span style="color:#66d9ef">return</span> <span style="color:#f92672">(</span><span style="color:#66d9ef">int</span><span style="color:#f92672">)(</span>value<span style="color:#f92672">^(</span>value<span style="color:#f92672">&gt;&gt;&gt;</span>32<span style="color:#f92672">));</span>
</span></span><span style="display:flex;"><span><span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>
</span></span><span style="display:flex;"><span>
</span></span><span style="display:flex;"><span><span style="color:#66d9ef">public</span> <span style="color:#66d9ef">static</span> <span style="color:#66d9ef">int</span> <span style="color:#a6e22e">hashCode</span><span style="color:#f92672">(</span><span style="color:#66d9ef">double</span> value<span style="color:#f92672">){</span>
</span></span><span style="display:flex;"><span>     <span style="color:#66d9ef">long</span> bits <span style="color:#f92672">=</span> doubleToLongBits<span style="color:#f92672">(</span>value<span style="color:#f92672">);</span>
</span></span><span style="display:flex;"><span>     <span style="color:#66d9ef">return</span> <span style="color:#f92672">(</span><span style="color:#66d9ef">int</span><span style="color:#f92672">)(</span>bits <span style="color:#f92672">^</span> <span style="color:#f92672">*(</span>bits<span style="color:#f92672">&gt;&gt;&gt;</span>32<span style="color:#f92672">));</span>
</span></span><span style="display:flex;"><span><span style="color:#f92672">}</span>
</span></span></code></pre></div><blockquote>
<p><strong>&raquo;&gt; 和 ^ 的作用是？</strong></p>
<p>高32bit和低32bit混合计算出32bit的哈希值
充分利用所有信息计算出哈希值</p>
</blockquote>
<h4 id="字符串类型">字符串类型</h4>
<p>整数5489是如何计算出来的？
<code>5*10^3+4*10^2+8*10^1+9*10^0</code></p>
<p>字符串是由若干个字符组成的
比如字符串jack由j、a、c、k四个字符组成（字符的本质就是一个整数）
因此jack的哈希值可以表示为
<code>j*n^3+a*n^2+c*n^1+k*n^0</code>
等价</p>
<p><code>[(j*n+a)*n+c]*n+k</code></p>
<p>在JDK中，乘数n为31，为什么使用31
31是奇素数,统计表明使用这个奇素数能让哈希分布更均匀,JVM会将31*i优化成(1&laquo;5)-1</p>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4;"><code class="language-java" data-lang="java"><span style="display:flex;"><span>String string <span style="color:#f92672">=</span> <span style="color:#e6db74">&#34;jack&#34;</span><span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span><span style="color:#66d9ef">int</span> hashCode <span style="color:#f92672">=</span> 0<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span><span style="color:#66d9ef">int</span> len <span style="color:#f92672">=</span> string<span style="color:#f92672">.</span><span style="color:#a6e22e">length</span><span style="color:#f92672">();</span>
</span></span><span style="display:flex;"><span><span style="color:#66d9ef">for</span><span style="color:#f92672">(</span><span style="color:#66d9ef">int</span> i<span style="color:#f92672">=</span>0<span style="color:#f92672">;</span>i<span style="color:#f92672">&lt;</span>len<span style="color:#f92672">;</span>i<span style="color:#f92672">++){</span>
</span></span><span style="display:flex;"><span>	<span style="color:#66d9ef">char</span> c <span style="color:#f92672">=</span> string<span style="color:#f92672">.</span><span style="color:#a6e22e">charAt</span><span style="color:#f92672">(</span>i<span style="color:#f92672">);</span>
</span></span><span style="display:flex;"><span>	hashCode <span style="color:#f92672">=</span> 31<span style="color:#f92672">*</span>hashCode<span style="color:#f92672">+</span>c<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span><span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>System<span style="color:#f92672">.</span><span style="color:#a6e22e">out</span><span style="color:#f92672">.</span><span style="color:#a6e22e">println</span><span style="color:#f92672">(</span>hashCode<span style="color:#f92672">);</span>
</span></span><span style="display:flex;"><span>System<span style="color:#f92672">.</span><span style="color:#a6e22e">out</span><span style="color:#f92672">.</span><span style="color:#a6e22e">println</span><span style="color:#f92672">(</span>string<span style="color:#f92672">.</span><span style="color:#a6e22e">hashCode</span><span style="color:#f92672">());</span>
</span></span></code></pre></div><h4 id="自定义对象的哈希值">自定义对象的哈希值</h4>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4;"><code class="language-java" data-lang="java"><span style="display:flex;"><span><span style="color:#66d9ef">public</span> <span style="color:#66d9ef">class</span> <span style="color:#a6e22e">Person</span><span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>	<span style="color:#66d9ef">private</span> <span style="color:#66d9ef">int</span> age<span style="color:#f92672">;</span>   
</span></span><span style="display:flex;"><span>	<span style="color:#66d9ef">private</span> <span style="color:#66d9ef">float</span> height<span style="color:#f92672">;</span> 
</span></span><span style="display:flex;"><span>	<span style="color:#66d9ef">private</span> String name<span style="color:#f92672">;</span> 
</span></span><span style="display:flex;"><span>	
</span></span><span style="display:flex;"><span>	<span style="color:#66d9ef">public</span> <span style="color:#a6e22e">Person</span><span style="color:#f92672">(</span><span style="color:#66d9ef">int</span> age<span style="color:#f92672">,</span> <span style="color:#66d9ef">float</span> height<span style="color:#f92672">,</span> String name<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>		<span style="color:#66d9ef">this</span><span style="color:#f92672">.</span><span style="color:#a6e22e">age</span> <span style="color:#f92672">=</span> age<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>		<span style="color:#66d9ef">this</span><span style="color:#f92672">.</span><span style="color:#a6e22e">height</span> <span style="color:#f92672">=</span> height<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>		<span style="color:#66d9ef">this</span><span style="color:#f92672">.</span><span style="color:#a6e22e">name</span> <span style="color:#f92672">=</span> name<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>	<span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>	
</span></span><span style="display:flex;"><span>	<span style="color:#a6e22e">@Override</span>
</span></span><span style="display:flex;"><span>	<span style="color:#75715e">/**
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">	 * 用来比较2个对象是否相等
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">	 */</span>
</span></span><span style="display:flex;"><span>	<span style="color:#66d9ef">public</span> <span style="color:#66d9ef">boolean</span> <span style="color:#a6e22e">equals</span><span style="color:#f92672">(</span>Object obj<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>		<span style="color:#75715e">// 内存地址
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>		<span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span><span style="color:#66d9ef">this</span> <span style="color:#f92672">==</span> obj<span style="color:#f92672">)</span> <span style="color:#66d9ef">return</span> <span style="color:#66d9ef">true</span><span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>		<span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>obj <span style="color:#f92672">==</span> <span style="color:#66d9ef">null</span> <span style="color:#f92672">||</span> obj<span style="color:#f92672">.</span><span style="color:#a6e22e">getClass</span><span style="color:#f92672">()</span> <span style="color:#f92672">!=</span> getClass<span style="color:#f92672">())</span> <span style="color:#66d9ef">return</span> <span style="color:#66d9ef">false</span><span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>		
</span></span><span style="display:flex;"><span>		<span style="color:#75715e">// 比较成员变量
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>		Person person <span style="color:#f92672">=</span> <span style="color:#f92672">(</span>Person<span style="color:#f92672">)</span> obj<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>		<span style="color:#66d9ef">return</span> person<span style="color:#f92672">.</span><span style="color:#a6e22e">age</span> <span style="color:#f92672">==</span> age
</span></span><span style="display:flex;"><span>				<span style="color:#f92672">&amp;&amp;</span> person<span style="color:#f92672">.</span><span style="color:#a6e22e">height</span> <span style="color:#f92672">==</span> height
</span></span><span style="display:flex;"><span>				<span style="color:#f92672">&amp;&amp;</span> <span style="color:#f92672">(</span>person<span style="color:#f92672">.</span><span style="color:#a6e22e">name</span> <span style="color:#f92672">==</span> <span style="color:#66d9ef">null</span> <span style="color:#f92672">?</span> name <span style="color:#f92672">==</span> <span style="color:#66d9ef">null</span> <span style="color:#f92672">:</span> person<span style="color:#f92672">.</span><span style="color:#a6e22e">name</span><span style="color:#f92672">.</span><span style="color:#a6e22e">equals</span><span style="color:#f92672">(</span>name<span style="color:#f92672">));</span>
</span></span><span style="display:flex;"><span>	<span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>	
</span></span><span style="display:flex;"><span>	<span style="color:#75715e">//所有字段都需要参与到计算中来,参考String
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>	<span style="color:#a6e22e">@Override</span>
</span></span><span style="display:flex;"><span>	<span style="color:#66d9ef">public</span> <span style="color:#66d9ef">int</span> <span style="color:#a6e22e">hashCode</span><span style="color:#f92672">()</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>		<span style="color:#66d9ef">int</span> hashCode <span style="color:#f92672">=</span> Integer<span style="color:#f92672">.</span><span style="color:#a6e22e">hashCode</span><span style="color:#f92672">(</span>age<span style="color:#f92672">);</span>
</span></span><span style="display:flex;"><span>		hashCode <span style="color:#f92672">=</span> hashCode <span style="color:#f92672">*</span> 31 <span style="color:#f92672">+</span> Float<span style="color:#f92672">.</span><span style="color:#a6e22e">hashCode</span><span style="color:#f92672">(</span>height<span style="color:#f92672">);</span>
</span></span><span style="display:flex;"><span>		hashCode <span style="color:#f92672">=</span> hashCode <span style="color:#f92672">*</span> 31 <span style="color:#f92672">+</span> <span style="color:#f92672">(</span>name <span style="color:#f92672">!=</span> <span style="color:#66d9ef">null</span> <span style="color:#f92672">?</span> name<span style="color:#f92672">.</span><span style="color:#a6e22e">hashCode</span><span style="color:#f92672">()</span> <span style="color:#f92672">:</span> 0<span style="color:#f92672">);</span>
</span></span><span style="display:flex;"><span>		<span style="color:#66d9ef">return</span> hashCode<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>	<span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span><span style="color:#f92672">}</span>
</span></span></code></pre></div><h2 id="put方法源码解析">put方法源码解析</h2>
<p>源码👇👇👇</p>
<p><img src="https://czh-pic.oss-cn-guangzhou.aliyuncs.com/202302181157769.png" alt="image-20230218115733812"></p>
<p>putVal()方法源码👇👇👇</p>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4;"><code class="language-java" data-lang="java"><span style="display:flex;"><span><span style="color:#75715e">/**
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * Implements Map.put and related methods
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> *
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * @param hash hash for key
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * @param key the key
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * @param value the value to put
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * @param onlyIfAbsent if true, don&#39;t change existing value
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * @param evict if false, the table is in creation mode.
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * @return previous value, or null if none
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> */</span>
</span></span><span style="display:flex;"><span><span style="color:#66d9ef">final</span> V <span style="color:#a6e22e">putVal</span><span style="color:#f92672">(</span><span style="color:#66d9ef">int</span> hash<span style="color:#f92672">,</span> K key<span style="color:#f92672">,</span> V value<span style="color:#f92672">,</span> <span style="color:#66d9ef">boolean</span> onlyIfAbsent<span style="color:#f92672">,</span>
</span></span><span style="display:flex;"><span>                   <span style="color:#66d9ef">boolean</span> evict<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>    Node<span style="color:#f92672">&lt;</span>K<span style="color:#f92672">,</span>V<span style="color:#f92672">&gt;[]</span> tab<span style="color:#f92672">;</span> Node<span style="color:#f92672">&lt;</span>K<span style="color:#f92672">,</span>V<span style="color:#f92672">&gt;</span> p<span style="color:#f92672">;</span> <span style="color:#66d9ef">int</span> n<span style="color:#f92672">,</span> i<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>    <span style="color:#75715e">/**
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">         * 先判断成员变量table是否为空且数组长度是否为0,如果这个条件满足说明还没有初始化，需要进行初始化
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">         */</span>
</span></span><span style="display:flex;"><span>    <span style="color:#66d9ef">if</span> <span style="color:#f92672">((</span>tab <span style="color:#f92672">=</span> table<span style="color:#f92672">)</span> <span style="color:#f92672">==</span> <span style="color:#66d9ef">null</span> <span style="color:#f92672">||</span> <span style="color:#f92672">(</span>n <span style="color:#f92672">=</span> tab<span style="color:#f92672">.</span><span style="color:#a6e22e">length</span><span style="color:#f92672">)</span> <span style="color:#f92672">==</span> 0<span style="color:#f92672">)</span>
</span></span><span style="display:flex;"><span>        <span style="color:#75715e">//调用resize()方法进行数组初始化操作
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>        n <span style="color:#f92672">=</span> <span style="color:#f92672">(</span>tab <span style="color:#f92672">=</span> resize<span style="color:#f92672">()).</span><span style="color:#a6e22e">length</span><span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>    <span style="color:#75715e">/**
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">         *  n:表示的是数组长度,前面方法中获取的.
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">         *  hash:传入的key的hash值
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">         *  i = (n-1) &amp; hash : 计算出这个key在数组中的索引位置【使用位运算更高效】
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">         *  如果这个索引位置上的元素为空，那把新添加的元素直接放到这个位置上
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">         */</span>
</span></span><span style="display:flex;"><span>    <span style="color:#66d9ef">if</span> <span style="color:#f92672">((</span>p <span style="color:#f92672">=</span> tab<span style="color:#f92672">[</span>i <span style="color:#f92672">=</span> <span style="color:#f92672">(</span>n <span style="color:#f92672">-</span> 1<span style="color:#f92672">)</span> <span style="color:#f92672">&amp;</span> hash<span style="color:#f92672">])</span> <span style="color:#f92672">==</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">)</span>
</span></span><span style="display:flex;"><span>        <span style="color:#75715e">//这个索引位置上就存放一个新的Node对象
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>        tab<span style="color:#f92672">[</span>i<span style="color:#f92672">]</span> <span style="color:#f92672">=</span> newNode<span style="color:#f92672">(</span>hash<span style="color:#f92672">,</span> key<span style="color:#f92672">,</span> value<span style="color:#f92672">,</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">);</span>
</span></span><span style="display:flex;"><span>    <span style="color:#75715e">/**
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">         * 来到这个判断，说明这个key计算出来的索引位置已经有元素了。
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">         * 属于hash碰撞的情况，这时候就会出现链表和红黑树了.
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">         */</span>
</span></span><span style="display:flex;"><span>    <span style="color:#66d9ef">else</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>        Node<span style="color:#f92672">&lt;</span>K<span style="color:#f92672">,</span>V<span style="color:#f92672">&gt;</span> e<span style="color:#f92672">;</span> K k<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>        <span style="color:#75715e">/**
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">             * 这段逻辑是判断当前传入的元素和链表/红黑树上的首元素是否为同一个元素，如果是就直接覆盖，如果不是那就需要往链表/红黑树上添加元素
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">             * 在HashMap中如何判断两个对象是否为同一个对象呢?
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">             * 1.两者的hash值相同
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">             * 2.两者的key内存地址一样 或者 两者的equals相同
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">             */</span>
</span></span><span style="display:flex;"><span>        <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>p<span style="color:#f92672">.</span><span style="color:#a6e22e">hash</span> <span style="color:#f92672">==</span> hash <span style="color:#f92672">&amp;&amp;</span>
</span></span><span style="display:flex;"><span>            <span style="color:#f92672">((</span>k <span style="color:#f92672">=</span> p<span style="color:#f92672">.</span><span style="color:#a6e22e">key</span><span style="color:#f92672">)</span> <span style="color:#f92672">==</span> key <span style="color:#f92672">||</span> <span style="color:#f92672">(</span>key <span style="color:#f92672">!=</span> <span style="color:#66d9ef">null</span> <span style="color:#f92672">&amp;&amp;</span> key<span style="color:#f92672">.</span><span style="color:#a6e22e">equals</span><span style="color:#f92672">(</span>k<span style="color:#f92672">))))</span>
</span></span><span style="display:flex;"><span>            e <span style="color:#f92672">=</span> p<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>        <span style="color:#75715e">/**
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">             * 来到这个判断逻辑,说明数组位置上的首元素和传入的元素并不是同一个对象
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">             * 这时候需要判断这个位置上的首元素是否红黑树节点
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">             */</span>
</span></span><span style="display:flex;"><span>        <span style="color:#66d9ef">else</span> <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>p <span style="color:#66d9ef">instanceof</span> TreeNode<span style="color:#f92672">)</span>
</span></span><span style="display:flex;"><span>            <span style="color:#75715e">//如果数组这个索引位置上的首元素是红黑树节点，那这样
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>            e <span style="color:#f92672">=</span> <span style="color:#f92672">((</span>TreeNode<span style="color:#f92672">&lt;</span>K<span style="color:#f92672">,</span>V<span style="color:#f92672">&gt;)</span>p<span style="color:#f92672">).</span><span style="color:#a6e22e">putTreeVal</span><span style="color:#f92672">(</span><span style="color:#66d9ef">this</span><span style="color:#f92672">,</span> tab<span style="color:#f92672">,</span> hash<span style="color:#f92672">,</span> key<span style="color:#f92672">,</span> value<span style="color:#f92672">);</span>
</span></span><span style="display:flex;"><span>        <span style="color:#75715e">/**
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">             * 如果来到这个判断逻辑，说明数组位置上的首元素和传入的元素并不是同一个对象且首元素并不是红黑树节点
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">             * 说明数组上存储的是链表
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">             */</span>
</span></span><span style="display:flex;"><span>        <span style="color:#66d9ef">else</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>            <span style="color:#75715e">/**
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">                 * 进行链表的遍历
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">                 */</span>
</span></span><span style="display:flex;"><span>            <span style="color:#66d9ef">for</span> <span style="color:#f92672">(</span><span style="color:#66d9ef">int</span> binCount <span style="color:#f92672">=</span> 0<span style="color:#f92672">;</span> <span style="color:#f92672">;</span> <span style="color:#f92672">++</span>binCount<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>                <span style="color:#66d9ef">if</span> <span style="color:#f92672">((</span>e <span style="color:#f92672">=</span> p<span style="color:#f92672">.</span><span style="color:#a6e22e">next</span><span style="color:#f92672">)</span> <span style="color:#f92672">==</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>                    <span style="color:#75715e">/*
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">                        来到这里，说明已经遍历完链表了，都没有元素和传入的元素相同
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">                        这时候就往链表的尾部添加一个新的Node对象
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">                         */</span>
</span></span><span style="display:flex;"><span>                    p<span style="color:#f92672">.</span><span style="color:#a6e22e">next</span> <span style="color:#f92672">=</span> newNode<span style="color:#f92672">(</span>hash<span style="color:#f92672">,</span> key<span style="color:#f92672">,</span> value<span style="color:#f92672">,</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">);</span>
</span></span><span style="display:flex;"><span>                    <span style="color:#75715e">/**
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">                         * 判断链表上的元素是否大于8【加入新添加的元素后个数为9】
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">                         * 如果大于，这个链表就转换成红黑树
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">                         */</span>
</span></span><span style="display:flex;"><span>                    <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>binCount <span style="color:#f92672">&gt;=</span> TREEIFY_THRESHOLD <span style="color:#f92672">-</span> 1<span style="color:#f92672">)</span> <span style="color:#75715e">// -1 for 1st
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>                        treeifyBin<span style="color:#f92672">(</span>tab<span style="color:#f92672">,</span> hash<span style="color:#f92672">);</span>
</span></span><span style="display:flex;"><span>                    <span style="color:#66d9ef">break</span><span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>                <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>                <span style="color:#75715e">/**
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">                     * 遍历的过程中判断链表上的元素和传入的元素是否为同一个元素
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">                     */</span>
</span></span><span style="display:flex;"><span>                <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>e<span style="color:#f92672">.</span><span style="color:#a6e22e">hash</span> <span style="color:#f92672">==</span> hash <span style="color:#f92672">&amp;&amp;</span>
</span></span><span style="display:flex;"><span>                    <span style="color:#f92672">((</span>k <span style="color:#f92672">=</span> e<span style="color:#f92672">.</span><span style="color:#a6e22e">key</span><span style="color:#f92672">)</span> <span style="color:#f92672">==</span> key <span style="color:#f92672">||</span> <span style="color:#f92672">(</span>key <span style="color:#f92672">!=</span> <span style="color:#66d9ef">null</span> <span style="color:#f92672">&amp;&amp;</span> key<span style="color:#f92672">.</span><span style="color:#a6e22e">equals</span><span style="color:#f92672">(</span>k<span style="color:#f92672">))))</span>
</span></span><span style="display:flex;"><span>                    <span style="color:#66d9ef">break</span><span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>                p <span style="color:#f92672">=</span> e<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>            <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>        <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>        <span style="color:#75715e">/**
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">             * 这里是进行值的覆盖，
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">             */</span>
</span></span><span style="display:flex;"><span>        <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>e <span style="color:#f92672">!=</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">)</span> <span style="color:#f92672">{</span> <span style="color:#75715e">// existing mapping for key
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>            V oldValue <span style="color:#f92672">=</span> e<span style="color:#f92672">.</span><span style="color:#a6e22e">value</span><span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>            <span style="color:#66d9ef">if</span> <span style="color:#f92672">(!</span>onlyIfAbsent <span style="color:#f92672">||</span> oldValue <span style="color:#f92672">==</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">)</span>
</span></span><span style="display:flex;"><span>                e<span style="color:#f92672">.</span><span style="color:#a6e22e">value</span> <span style="color:#f92672">=</span> value<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>            <span style="color:#75715e">//钩子函数，空实现，用于给其他类拓容用的.
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>            afterNodeAccess<span style="color:#f92672">(</span>e<span style="color:#f92672">);</span>
</span></span><span style="display:flex;"><span>            <span style="color:#66d9ef">return</span> oldValue<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>        <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>    <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>    <span style="color:#f92672">++</span>modCount<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>    <span style="color:#75715e">//添加完之后,size增加，判断是否大于拓容阈值
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>    <span style="color:#66d9ef">if</span> <span style="color:#f92672">(++</span>size <span style="color:#f92672">&gt;</span> threshold<span style="color:#f92672">)</span>
</span></span><span style="display:flex;"><span>        resize<span style="color:#f92672">();</span>
</span></span><span style="display:flex;"><span>    <span style="color:#75715e">//钩子方法，空实现
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>    afterNodeInsertion<span style="color:#f92672">(</span>evict<span style="color:#f92672">);</span>
</span></span><span style="display:flex;"><span>    <span style="color:#66d9ef">return</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span><span style="color:#f92672">}</span>
</span></span></code></pre></div><hr>
<p><strong>其中，包含的方法源码与成员变量及常量：</strong></p>
<ul>
<li>常量：MAXIMUM_CAPACITY（最大容量）</li>
</ul>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4;"><code class="language-java" data-lang="java"><span style="display:flex;"><span><span style="color:#75715e">/**
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * The maximum capacity, used if a higher value is implicitly specified
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * by either of the constructors with arguments.
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * MUST be a power of two &lt;= 1&lt;&lt;30.
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> */</span>
</span></span><span style="display:flex;"><span><span style="color:#66d9ef">static</span> <span style="color:#66d9ef">final</span> <span style="color:#66d9ef">int</span> MAXIMUM_CAPACITY <span style="color:#f92672">=</span> 1 <span style="color:#f92672">&lt;&lt;</span> 30<span style="color:#f92672">;</span>
</span></span></code></pre></div><ul>
<li>常量：DEFAULT_INITIAL_CAPACITY（默认初始容量）</li>
</ul>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4;"><code class="language-java" data-lang="java"><span style="display:flex;"><span><span style="color:#75715e">/**
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * The default initial capacity - MUST be a power of two.
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> */</span>
</span></span><span style="display:flex;"><span><span style="color:#66d9ef">static</span> <span style="color:#66d9ef">final</span> <span style="color:#66d9ef">int</span> DEFAULT_INITIAL_CAPACITY <span style="color:#f92672">=</span> 1 <span style="color:#f92672">&lt;&lt;</span> 4<span style="color:#f92672">;</span> <span style="color:#75715e">// aka 16
</span></span></span></code></pre></div><ul>
<li>常量：DEFAULT_LOAD_FACTOR（默认负载因子）</li>
</ul>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4;"><code class="language-java" data-lang="java"><span style="display:flex;"><span><span style="color:#75715e">/**
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * The load factor used when none specified in constructor.
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> */</span>
</span></span><span style="display:flex;"><span><span style="color:#66d9ef">static</span> <span style="color:#66d9ef">final</span> <span style="color:#66d9ef">float</span> DEFAULT_LOAD_FACTOR <span style="color:#f92672">=</span> 0<span style="color:#f92672">.</span><span style="color:#a6e22e">75f</span><span style="color:#f92672">;</span>
</span></span></code></pre></div><ul>
<li>常量：TREEIFY_THRESHOLD（树形阈值）</li>
</ul>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4;"><code class="language-java" data-lang="java"><span style="display:flex;"><span><span style="color:#75715e">/**
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * The bin count threshold for using a tree rather than list for a
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * bin.  Bins are converted to trees when adding an element to a
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * bin with at least this many nodes. The value must be greater
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * than 2 and should be at least 8 to mesh with assumptions in
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * tree removal about conversion back to plain bins upon
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * shrinkage.
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> */</span>
</span></span><span style="display:flex;"><span><span style="color:#66d9ef">static</span> <span style="color:#66d9ef">final</span> <span style="color:#66d9ef">int</span> TREEIFY_THRESHOLD <span style="color:#f92672">=</span> 8<span style="color:#f92672">;</span>
</span></span></code></pre></div><ul>
<li>成员变量：table</li>
</ul>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4;"><code class="language-java" data-lang="java"><span style="display:flex;"><span><span style="color:#75715e">/**
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * The table, initialized on first use, and resized as
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * necessary. When allocated, length is always a power of two.
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * (We also tolerate length zero in some operations to allow
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * bootstrapping mechanics that are currently not needed.)
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> */</span>
</span></span><span style="display:flex;"><span><span style="color:#66d9ef">transient</span> Node<span style="color:#f92672">&lt;</span>K<span style="color:#f92672">,</span>V<span style="color:#f92672">&gt;[]</span> table<span style="color:#f92672">;</span>
</span></span></code></pre></div><ul>
<li>成员变量：threshold（扩容阈值）</li>
</ul>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4;"><code class="language-java" data-lang="java"><span style="display:flex;"><span><span style="color:#75715e">/**
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * The next size value at which to resize (capacity * load factor).
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> *
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * @serial
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> */</span>
</span></span><span style="display:flex;"><span><span style="color:#75715e">// (The javadoc description is true upon serialization.
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">// Additionally, if the table array has not been allocated, this
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">// field holds the initial array capacity, or zero signifying
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">// DEFAULT_INITIAL_CAPACITY.)
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span><span style="color:#66d9ef">int</span> threshold<span style="color:#f92672">;</span>
</span></span></code></pre></div><ul>
<li>成员变量：modCount</li>
</ul>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4;"><code class="language-java" data-lang="java"><span style="display:flex;"><span><span style="color:#75715e">/**
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * The number of times this HashMap has been structurally modified
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * Structural modifications are those that change the number of mappings in
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * the HashMap or otherwise modify its internal structure (e.g.,
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * rehash).  This field is used to make iterators on Collection-views of
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * the HashMap fail-fast.  (See ConcurrentModificationException).
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> */</span>
</span></span><span style="display:flex;"><span><span style="color:#66d9ef">transient</span> <span style="color:#66d9ef">int</span> modCount<span style="color:#f92672">;</span>
</span></span></code></pre></div><ul>
<li>方法resize()源码👇👇👇</li>
</ul>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4;"><code class="language-java" data-lang="java"><span style="display:flex;"><span><span style="color:#75715e">/**
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * Initializes or doubles table size.  If null, allocates in
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * accord with initial capacity target held in field threshold.
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * Otherwise, because we are using power-of-two expansion, the
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * elements from each bin must either stay at same index, or move
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * with a power of two offset in the new table.
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> *
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * @return the table
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> */</span>
</span></span><span style="display:flex;"><span><span style="color:#66d9ef">final</span> Node<span style="color:#f92672">&lt;</span>K<span style="color:#f92672">,</span>V<span style="color:#f92672">&gt;[]</span> <span style="color:#a6e22e">resize</span><span style="color:#f92672">()</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>    <span style="color:#75715e">//获取成员变量table赋值给局部变量oldTab,第一次进入的时候table=null.
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>    Node<span style="color:#f92672">&lt;</span>K<span style="color:#f92672">,</span>V<span style="color:#f92672">&gt;[]</span> oldTab <span style="color:#f92672">=</span> table<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>    <span style="color:#75715e">//由于第一次进入oldTable为空所以oldCap=0
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>    <span style="color:#66d9ef">int</span> oldCap <span style="color:#f92672">=</span> <span style="color:#f92672">(</span>oldTab <span style="color:#f92672">==</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">)</span> <span style="color:#f92672">?</span> 0 <span style="color:#f92672">:</span> oldTab<span style="color:#f92672">.</span><span style="color:#a6e22e">length</span><span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>    <span style="color:#75715e">//把成员变量threshold【拓容阈值】赋值给局部变量oldThr
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>    <span style="color:#66d9ef">int</span> oldThr <span style="color:#f92672">=</span> threshold<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>    <span style="color:#66d9ef">int</span> newCap<span style="color:#f92672">,</span> newThr <span style="color:#f92672">=</span> 0<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>    <span style="color:#75715e">//判断旧数组长度是否大于0,这段逻辑是数组拓容的逻辑，第一次进入的时候不会执行
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>    <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>oldCap <span style="color:#f92672">&gt;</span> 0<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>        <span style="color:#75715e">/**
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">         * 拓容的时候会进入这个方法
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">         */</span>
</span></span><span style="display:flex;"><span>        <span style="color:#75715e">/**
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">         * 判断旧容量是否已经大于最大容量了，如果是的话就不在拓容了
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">         */</span>
</span></span><span style="display:flex;"><span>        <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>oldCap <span style="color:#f92672">&gt;=</span> MAXIMUM_CAPACITY<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>            threshold <span style="color:#f92672">=</span> Integer<span style="color:#f92672">.</span><span style="color:#a6e22e">MAX_VALUE</span><span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>            <span style="color:#66d9ef">return</span> oldTab<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>        <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>        <span style="color:#75715e">/**
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">         * oldCap &lt;&lt; 1   其实就是oldCap * 2的操作，只是使用位运算性能更好
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">         * 拓容的时候其实就是新容量=旧容量*2
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">         */</span>
</span></span><span style="display:flex;"><span>        <span style="color:#66d9ef">else</span> <span style="color:#66d9ef">if</span> <span style="color:#f92672">((</span>newCap <span style="color:#f92672">=</span> oldCap <span style="color:#f92672">&lt;&lt;</span> 1<span style="color:#f92672">)</span> <span style="color:#f92672">&lt;</span> MAXIMUM_CAPACITY <span style="color:#f92672">&amp;&amp;</span>
</span></span><span style="display:flex;"><span>                 oldCap <span style="color:#f92672">&gt;=</span> DEFAULT_INITIAL_CAPACITY<span style="color:#f92672">)</span>
</span></span><span style="display:flex;"><span>            <span style="color:#75715e">//拓容阈值=原来的拓容阈值* 2
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>            newThr <span style="color:#f92672">=</span> oldThr <span style="color:#f92672">&lt;&lt;</span> 1<span style="color:#f92672">;</span> <span style="color:#75715e">// double threshold
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>    <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>    <span style="color:#66d9ef">else</span> <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>oldThr <span style="color:#f92672">&gt;</span> 0<span style="color:#f92672">)</span> <span style="color:#75715e">// initial capacity was placed in threshold
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>        newCap <span style="color:#f92672">=</span> oldThr<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>    <span style="color:#66d9ef">else</span> <span style="color:#f92672">{</span>               <span style="color:#75715e">// zero initial threshold signifies using defaults
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>        <span style="color:#75715e">/**
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">         * 第一次初始化的时候执行这段逻辑
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">         * newCap表示初始化数组的长度默认为16.
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">         * newThr表示拓容阈值=数组长度*0.75
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">         *
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">         */</span>
</span></span><span style="display:flex;"><span>        newCap <span style="color:#f92672">=</span> DEFAULT_INITIAL_CAPACITY<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>        newThr <span style="color:#f92672">=</span> <span style="color:#f92672">(</span><span style="color:#66d9ef">int</span><span style="color:#f92672">)(</span>DEFAULT_LOAD_FACTOR <span style="color:#f92672">*</span> DEFAULT_INITIAL_CAPACITY<span style="color:#f92672">);</span>
</span></span><span style="display:flex;"><span>    <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>    <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>newThr <span style="color:#f92672">==</span> 0<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>        <span style="color:#66d9ef">float</span> ft <span style="color:#f92672">=</span> <span style="color:#f92672">(</span><span style="color:#66d9ef">float</span><span style="color:#f92672">)</span>newCap <span style="color:#f92672">*</span> loadFactor<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>        newThr <span style="color:#f92672">=</span> <span style="color:#f92672">(</span>newCap <span style="color:#f92672">&lt;</span> MAXIMUM_CAPACITY <span style="color:#f92672">&amp;&amp;</span> ft <span style="color:#f92672">&lt;</span> <span style="color:#f92672">(</span><span style="color:#66d9ef">float</span><span style="color:#f92672">)</span>MAXIMUM_CAPACITY <span style="color:#f92672">?</span>
</span></span><span style="display:flex;"><span>                  <span style="color:#f92672">(</span><span style="color:#66d9ef">int</span><span style="color:#f92672">)</span>ft <span style="color:#f92672">:</span> Integer<span style="color:#f92672">.</span><span style="color:#a6e22e">MAX_VALUE</span><span style="color:#f92672">);</span>
</span></span><span style="display:flex;"><span>    <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>    threshold <span style="color:#f92672">=</span> newThr<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>    <span style="color:#a6e22e">@SuppressWarnings</span><span style="color:#f92672">({</span><span style="color:#e6db74">&#34;rawtypes&#34;</span><span style="color:#f92672">,</span><span style="color:#e6db74">&#34;unchecked&#34;</span><span style="color:#f92672">})</span>
</span></span><span style="display:flex;"><span>        <span style="color:#75715e">//新建长度为newCap的Node数组
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>        Node<span style="color:#f92672">&lt;</span>K<span style="color:#f92672">,</span>V<span style="color:#f92672">&gt;[]</span> newTab <span style="color:#f92672">=</span> <span style="color:#f92672">(</span>Node<span style="color:#f92672">&lt;</span>K<span style="color:#f92672">,</span>V<span style="color:#f92672">&gt;[])</span><span style="color:#66d9ef">new</span> Node<span style="color:#f92672">[</span>newCap<span style="color:#f92672">];</span>
</span></span><span style="display:flex;"><span>    <span style="color:#75715e">//把新建出来的数组赋值给局部变量
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>    table <span style="color:#f92672">=</span> newTab<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>    <span style="color:#75715e">//第一次初始化,oldTable=null,所以就不会执行后续代码了.
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>    <span style="color:#75715e">//这段逻辑是拓容的逻辑
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>    <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>oldTab <span style="color:#f92672">!=</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>        <span style="color:#75715e">//循环遍历整个数组
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>        <span style="color:#66d9ef">for</span> <span style="color:#f92672">(</span><span style="color:#66d9ef">int</span> j <span style="color:#f92672">=</span> 0<span style="color:#f92672">;</span> j <span style="color:#f92672">&lt;</span> oldCap<span style="color:#f92672">;</span> <span style="color:#f92672">++</span>j<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>            Node<span style="color:#f92672">&lt;</span>K<span style="color:#f92672">,</span>V<span style="color:#f92672">&gt;</span> e<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>            <span style="color:#75715e">//如果数组上有元素才需要对这个数组上的元素进行迁移，如果没有的话直接下一个.
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>            <span style="color:#66d9ef">if</span> <span style="color:#f92672">((</span>e <span style="color:#f92672">=</span> oldTab<span style="color:#f92672">[</span>j<span style="color:#f92672">])</span> <span style="color:#f92672">!=</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>                oldTab<span style="color:#f92672">[</span>j<span style="color:#f92672">]</span> <span style="color:#f92672">=</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>                <span style="color:#75715e">/**
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">                 * 如果数组上只有一个元素，直接把这个元素放入到新数组的位置
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">                 * 新数组的位置其实就是拿到hash值根据新数组的长度进行运算
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">                 */</span>
</span></span><span style="display:flex;"><span>                <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>e<span style="color:#f92672">.</span><span style="color:#a6e22e">next</span> <span style="color:#f92672">==</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">)</span>
</span></span><span style="display:flex;"><span>                    newTab<span style="color:#f92672">[</span>e<span style="color:#f92672">.</span><span style="color:#a6e22e">hash</span> <span style="color:#f92672">&amp;</span> <span style="color:#f92672">(</span>newCap <span style="color:#f92672">-</span> 1<span style="color:#f92672">)]</span> <span style="color:#f92672">=</span> e<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>                <span style="color:#75715e">//判断数组首元素是否为红黑树节点
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>                <span style="color:#66d9ef">else</span> <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>e <span style="color:#66d9ef">instanceof</span> TreeNode<span style="color:#f92672">)</span>
</span></span><span style="display:flex;"><span>                    <span style="color:#75715e">//拓容的话，需要对红黑树进行分割操作
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>                    <span style="color:#f92672">((</span>TreeNode<span style="color:#f92672">&lt;</span>K<span style="color:#f92672">,</span>V<span style="color:#f92672">&gt;)</span>e<span style="color:#f92672">).</span><span style="color:#a6e22e">split</span><span style="color:#f92672">(</span><span style="color:#66d9ef">this</span><span style="color:#f92672">,</span> newTab<span style="color:#f92672">,</span> j<span style="color:#f92672">,</span> oldCap<span style="color:#f92672">);</span>
</span></span><span style="display:flex;"><span>                <span style="color:#75715e">//来到这个逻辑说明是链表
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>                <span style="color:#66d9ef">else</span> <span style="color:#f92672">{</span> <span style="color:#75715e">// preserve order
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>                    <span style="color:#75715e">/**
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">                     * 这段逻辑其实就是分割链表，分割为低位链表和高位链表。
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">                     * 低位链表存储在新数组的j位置，高位链表存储在新数组的j+n位置【n是旧数组长度】
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">                     */</span>
</span></span><span style="display:flex;"><span>                    <span style="color:#75715e">//定义低位链表头和低位链表尾
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>                    Node<span style="color:#f92672">&lt;</span>K<span style="color:#f92672">,</span>V<span style="color:#f92672">&gt;</span> loHead <span style="color:#f92672">=</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">,</span> loTail <span style="color:#f92672">=</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>                    <span style="color:#75715e">//定义高位链表头和高位链表尾
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>                    Node<span style="color:#f92672">&lt;</span>K<span style="color:#f92672">,</span>V<span style="color:#f92672">&gt;</span> hiHead <span style="color:#f92672">=</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">,</span> hiTail <span style="color:#f92672">=</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>                    Node<span style="color:#f92672">&lt;</span>K<span style="color:#f92672">,</span>V<span style="color:#f92672">&gt;</span> next<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>                    <span style="color:#66d9ef">do</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>                        <span style="color:#75715e">//进行链表遍历
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>                        next <span style="color:#f92672">=</span> e<span style="color:#f92672">.</span><span style="color:#a6e22e">next</span><span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>                        <span style="color:#75715e">/**
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">                         *  (e.hash &amp; oldCap) == 0 说明这个元素存储在低位链表
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">                         *  (e.hash &amp; oldCap) == 1 说明这个元素存储在高位链表
</span></span></span><span style="display:flex;"><span><span style="color:#75715e">                         */</span>
</span></span><span style="display:flex;"><span>                        <span style="color:#66d9ef">if</span> <span style="color:#f92672">((</span>e<span style="color:#f92672">.</span><span style="color:#a6e22e">hash</span> <span style="color:#f92672">&amp;</span> oldCap<span style="color:#f92672">)</span> <span style="color:#f92672">==</span> 0<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>                            <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>loTail <span style="color:#f92672">==</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">)</span>
</span></span><span style="display:flex;"><span>                                loHead <span style="color:#f92672">=</span> e<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>                            <span style="color:#66d9ef">else</span>
</span></span><span style="display:flex;"><span>                                loTail<span style="color:#f92672">.</span><span style="color:#a6e22e">next</span> <span style="color:#f92672">=</span> e<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>                            loTail <span style="color:#f92672">=</span> e<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>                        <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>                        <span style="color:#66d9ef">else</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>                            <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>hiTail <span style="color:#f92672">==</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">)</span>
</span></span><span style="display:flex;"><span>                                hiHead <span style="color:#f92672">=</span> e<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>                            <span style="color:#66d9ef">else</span>
</span></span><span style="display:flex;"><span>                                hiTail<span style="color:#f92672">.</span><span style="color:#a6e22e">next</span> <span style="color:#f92672">=</span> e<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>                            hiTail <span style="color:#f92672">=</span> e<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>                        <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>                    <span style="color:#f92672">}</span> <span style="color:#66d9ef">while</span> <span style="color:#f92672">((</span>e <span style="color:#f92672">=</span> next<span style="color:#f92672">)</span> <span style="color:#f92672">!=</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">);</span>
</span></span><span style="display:flex;"><span>                    <span style="color:#75715e">//如果低位链表的尾部不为空，说明有低位链表，这时候在新数组的j位置添加低位链表的头元素
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>                    <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>loTail <span style="color:#f92672">!=</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>                        loTail<span style="color:#f92672">.</span><span style="color:#a6e22e">next</span> <span style="color:#f92672">=</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>                        newTab<span style="color:#f92672">[</span>j<span style="color:#f92672">]</span> <span style="color:#f92672">=</span> loHead<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>                    <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>                    <span style="color:#75715e">//如果高位链表的尾部不为空，说明有高位链表，这时候在新数组的j+n位置添加高位链表的头元素
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>                    <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>hiTail <span style="color:#f92672">!=</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>                        hiTail<span style="color:#f92672">.</span><span style="color:#a6e22e">next</span> <span style="color:#f92672">=</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>                        newTab<span style="color:#f92672">[</span>j <span style="color:#f92672">+</span> oldCap<span style="color:#f92672">]</span> <span style="color:#f92672">=</span> hiHead<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>                    <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>                <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>            <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>        <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>    <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>    <span style="color:#66d9ef">return</span> newTab<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span><span style="color:#f92672">}</span>
</span></span></code></pre></div><p>方法treeifyBin()源码👇👇👇</p>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4;"><code class="language-java" data-lang="java"><span style="display:flex;"><span><span style="color:#75715e">/**
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * Replaces all linked nodes in bin at index for given hash unless
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * table is too small, in which case resizes instead.
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> */</span>
</span></span><span style="display:flex;"><span><span style="color:#75715e">/**
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * 当链表长度&gt;8的时候,会来到这个树化方法
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> */</span>
</span></span><span style="display:flex;"><span><span style="color:#66d9ef">final</span> <span style="color:#66d9ef">void</span> <span style="color:#a6e22e">treeifyBin</span><span style="color:#f92672">(</span>Node<span style="color:#f92672">&lt;</span>K<span style="color:#f92672">,</span>V<span style="color:#f92672">&gt;[]</span> tab<span style="color:#f92672">,</span> <span style="color:#66d9ef">int</span> hash<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>    <span style="color:#66d9ef">int</span> n<span style="color:#f92672">,</span> index<span style="color:#f92672">;</span> Node<span style="color:#f92672">&lt;</span>K<span style="color:#f92672">,</span>V<span style="color:#f92672">&gt;</span> e<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>    <span style="color:#75715e">//如果数组长度&lt;64的情况，链表并不会变成红黑树,而是进行拓容操作
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>    <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>tab <span style="color:#f92672">==</span> <span style="color:#66d9ef">null</span> <span style="color:#f92672">||</span> <span style="color:#f92672">(</span>n <span style="color:#f92672">=</span> tab<span style="color:#f92672">.</span><span style="color:#a6e22e">length</span><span style="color:#f92672">)</span> <span style="color:#f92672">&lt;</span> MIN_TREEIFY_CAPACITY<span style="color:#f92672">)</span>
</span></span><span style="display:flex;"><span>        resize<span style="color:#f92672">();</span>
</span></span><span style="display:flex;"><span>    <span style="color:#66d9ef">else</span> <span style="color:#66d9ef">if</span> <span style="color:#f92672">((</span>e <span style="color:#f92672">=</span> tab<span style="color:#f92672">[</span>index <span style="color:#f92672">=</span> <span style="color:#f92672">(</span>n <span style="color:#f92672">-</span> 1<span style="color:#f92672">)</span> <span style="color:#f92672">&amp;</span> hash<span style="color:#f92672">])</span> <span style="color:#f92672">!=</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>        TreeNode<span style="color:#f92672">&lt;</span>K<span style="color:#f92672">,</span>V<span style="color:#f92672">&gt;</span> hd <span style="color:#f92672">=</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">,</span> tl <span style="color:#f92672">=</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>        <span style="color:#75715e">//在正在变成红黑树之前，会将链表从单向链表变成双向链表.目的是方便遍历和操作
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>        <span style="color:#75715e">//所有里面技术红黑树的结构也是双向链表结构，添加时候使用红黑树特性，遍历的时候使用双向链表
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>        <span style="color:#66d9ef">do</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>            TreeNode<span style="color:#f92672">&lt;</span>K<span style="color:#f92672">,</span>V<span style="color:#f92672">&gt;</span> p <span style="color:#f92672">=</span> replacementTreeNode<span style="color:#f92672">(</span>e<span style="color:#f92672">,</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">);</span>
</span></span><span style="display:flex;"><span>            <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>tl <span style="color:#f92672">==</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">)</span>
</span></span><span style="display:flex;"><span>                hd <span style="color:#f92672">=</span> p<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>            <span style="color:#66d9ef">else</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>                p<span style="color:#f92672">.</span><span style="color:#a6e22e">prev</span> <span style="color:#f92672">=</span> tl<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>                tl<span style="color:#f92672">.</span><span style="color:#a6e22e">next</span> <span style="color:#f92672">=</span> p<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>            <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>            tl <span style="color:#f92672">=</span> p<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>        <span style="color:#f92672">}</span> <span style="color:#66d9ef">while</span> <span style="color:#f92672">((</span>e <span style="color:#f92672">=</span> e<span style="color:#f92672">.</span><span style="color:#a6e22e">next</span><span style="color:#f92672">)</span> <span style="color:#f92672">!=</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">);</span>
</span></span><span style="display:flex;"><span>        <span style="color:#66d9ef">if</span> <span style="color:#f92672">((</span>tab<span style="color:#f92672">[</span>index<span style="color:#f92672">]</span> <span style="color:#f92672">=</span> hd<span style="color:#f92672">)</span> <span style="color:#f92672">!=</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">)</span>
</span></span><span style="display:flex;"><span>            <span style="color:#75715e">//这个才是真正链表边红黑树的逻辑
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"></span>            hd<span style="color:#f92672">.</span><span style="color:#a6e22e">treeify</span><span style="color:#f92672">(</span>tab<span style="color:#f92672">);</span>
</span></span><span style="display:flex;"><span>    <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span><span style="color:#f92672">}</span>
</span></span></code></pre></div><p>方法treeify()源码👇👇👇</p>
<div class="highlight"><pre tabindex="0" style="color:#f8f8f2;background-color:#272822;-moz-tab-size:4;-o-tab-size:4;tab-size:4;"><code class="language-java" data-lang="java"><span style="display:flex;"><span><span style="color:#75715e">/**
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * Forms tree of the nodes linked from this node.
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> * @return root of tree
</span></span></span><span style="display:flex;"><span><span style="color:#75715e"> */</span>
</span></span><span style="display:flex;"><span><span style="color:#66d9ef">final</span> <span style="color:#66d9ef">void</span> <span style="color:#a6e22e">treeify</span><span style="color:#f92672">(</span>Node<span style="color:#f92672">&lt;</span>K<span style="color:#f92672">,</span>V<span style="color:#f92672">&gt;[]</span> tab<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>    TreeNode<span style="color:#f92672">&lt;</span>K<span style="color:#f92672">,</span>V<span style="color:#f92672">&gt;</span> root <span style="color:#f92672">=</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>    <span style="color:#66d9ef">for</span> <span style="color:#f92672">(</span>TreeNode<span style="color:#f92672">&lt;</span>K<span style="color:#f92672">,</span>V<span style="color:#f92672">&gt;</span> x <span style="color:#f92672">=</span> <span style="color:#66d9ef">this</span><span style="color:#f92672">,</span> next<span style="color:#f92672">;</span> x <span style="color:#f92672">!=</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">;</span> x <span style="color:#f92672">=</span> next<span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>        next <span style="color:#f92672">=</span> <span style="color:#f92672">(</span>TreeNode<span style="color:#f92672">&lt;</span>K<span style="color:#f92672">,</span>V<span style="color:#f92672">&gt;)</span>x<span style="color:#f92672">.</span><span style="color:#a6e22e">next</span><span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>        x<span style="color:#f92672">.</span><span style="color:#a6e22e">left</span> <span style="color:#f92672">=</span> x<span style="color:#f92672">.</span><span style="color:#a6e22e">right</span> <span style="color:#f92672">=</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>        <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>root <span style="color:#f92672">==</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>            x<span style="color:#f92672">.</span><span style="color:#a6e22e">parent</span> <span style="color:#f92672">=</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>            x<span style="color:#f92672">.</span><span style="color:#a6e22e">red</span> <span style="color:#f92672">=</span> <span style="color:#66d9ef">false</span><span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>            root <span style="color:#f92672">=</span> x<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>        <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>        <span style="color:#66d9ef">else</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>            K k <span style="color:#f92672">=</span> x<span style="color:#f92672">.</span><span style="color:#a6e22e">key</span><span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>            <span style="color:#66d9ef">int</span> h <span style="color:#f92672">=</span> x<span style="color:#f92672">.</span><span style="color:#a6e22e">hash</span><span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>            Class<span style="color:#f92672">&lt;?&gt;</span> kc <span style="color:#f92672">=</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>            <span style="color:#66d9ef">for</span> <span style="color:#f92672">(</span>TreeNode<span style="color:#f92672">&lt;</span>K<span style="color:#f92672">,</span>V<span style="color:#f92672">&gt;</span> p <span style="color:#f92672">=</span> root<span style="color:#f92672">;;)</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>                <span style="color:#66d9ef">int</span> dir<span style="color:#f92672">,</span> ph<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>                K pk <span style="color:#f92672">=</span> p<span style="color:#f92672">.</span><span style="color:#a6e22e">key</span><span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>                <span style="color:#66d9ef">if</span> <span style="color:#f92672">((</span>ph <span style="color:#f92672">=</span> p<span style="color:#f92672">.</span><span style="color:#a6e22e">hash</span><span style="color:#f92672">)</span> <span style="color:#f92672">&gt;</span> h<span style="color:#f92672">)</span>
</span></span><span style="display:flex;"><span>                    dir <span style="color:#f92672">=</span> <span style="color:#f92672">-</span>1<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>                <span style="color:#66d9ef">else</span> <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>ph <span style="color:#f92672">&lt;</span> h<span style="color:#f92672">)</span>
</span></span><span style="display:flex;"><span>                    dir <span style="color:#f92672">=</span> 1<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>                <span style="color:#66d9ef">else</span> <span style="color:#66d9ef">if</span> <span style="color:#f92672">((</span>kc <span style="color:#f92672">==</span> <span style="color:#66d9ef">null</span> <span style="color:#f92672">&amp;&amp;</span>
</span></span><span style="display:flex;"><span>                          <span style="color:#f92672">(</span>kc <span style="color:#f92672">=</span> comparableClassFor<span style="color:#f92672">(</span>k<span style="color:#f92672">))</span> <span style="color:#f92672">==</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">)</span> <span style="color:#f92672">||</span>
</span></span><span style="display:flex;"><span>                         <span style="color:#f92672">(</span>dir <span style="color:#f92672">=</span> compareComparables<span style="color:#f92672">(</span>kc<span style="color:#f92672">,</span> k<span style="color:#f92672">,</span> pk<span style="color:#f92672">))</span> <span style="color:#f92672">==</span> 0<span style="color:#f92672">)</span>
</span></span><span style="display:flex;"><span>                    dir <span style="color:#f92672">=</span> tieBreakOrder<span style="color:#f92672">(</span>k<span style="color:#f92672">,</span> pk<span style="color:#f92672">);</span>
</span></span><span style="display:flex;"><span>
</span></span><span style="display:flex;"><span>                TreeNode<span style="color:#f92672">&lt;</span>K<span style="color:#f92672">,</span>V<span style="color:#f92672">&gt;</span> xp <span style="color:#f92672">=</span> p<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>                <span style="color:#66d9ef">if</span> <span style="color:#f92672">((</span>p <span style="color:#f92672">=</span> <span style="color:#f92672">(</span>dir <span style="color:#f92672">&lt;=</span> 0<span style="color:#f92672">)</span> <span style="color:#f92672">?</span> p<span style="color:#f92672">.</span><span style="color:#a6e22e">left</span> <span style="color:#f92672">:</span> p<span style="color:#f92672">.</span><span style="color:#a6e22e">right</span><span style="color:#f92672">)</span> <span style="color:#f92672">==</span> <span style="color:#66d9ef">null</span><span style="color:#f92672">)</span> <span style="color:#f92672">{</span>
</span></span><span style="display:flex;"><span>                    x<span style="color:#f92672">.</span><span style="color:#a6e22e">parent</span> <span style="color:#f92672">=</span> xp<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>                    <span style="color:#66d9ef">if</span> <span style="color:#f92672">(</span>dir <span style="color:#f92672">&lt;=</span> 0<span style="color:#f92672">)</span>
</span></span><span style="display:flex;"><span>                        xp<span style="color:#f92672">.</span><span style="color:#a6e22e">left</span> <span style="color:#f92672">=</span> x<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>                    <span style="color:#66d9ef">else</span>
</span></span><span style="display:flex;"><span>                        xp<span style="color:#f92672">.</span><span style="color:#a6e22e">right</span> <span style="color:#f92672">=</span> x<span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>                    root <span style="color:#f92672">=</span> balanceInsertion<span style="color:#f92672">(</span>root<span style="color:#f92672">,</span> x<span style="color:#f92672">);</span>
</span></span><span style="display:flex;"><span>                    <span style="color:#66d9ef">break</span><span style="color:#f92672">;</span>
</span></span><span style="display:flex;"><span>                <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>            <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>        <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>    <span style="color:#f92672">}</span>
</span></span><span style="display:flex;"><span>    moveRootToFront<span style="color:#f92672">(</span>tab<span style="color:#f92672">,</span> root<span style="color:#f92672">);</span>
</span></span><span style="display:flex;"><span><span style="color:#f92672">}</span>
</span></span></code></pre></div><hr>
<p>描述：</p>
<p>现根据 key 的 hashCode（计算 hash 值的方法:int hash = hash(key.hashCode())，此方法加了高位运算，以防止 hash 冲突）重新计算 hash 值，然后再根据该 hash 值得到这个元素在数组中的位置（得到该 hash 值所对应 table 中索引的方法：int i = indexFor(hash,table.length)）（即下标）。如果该位置上没有元素，就直接将该元素放到此数组中的该位置上。若该位置上已经存放了其他元素了，则在该位置上的元素将以链表的形式存放，新加入的放在链表头，最先加入的放在链表尾。（把元素放到该索引位置上的方法：addEntry(hash,key,value,i)）。</p>
<h2 id="get方法源码解析">get方法源码解析</h2>
<p>描述：</p>
<p>从 HashMap 中 get 元素 时， 首先 根据 key 的 hashCode() 计算 key 的 hash 值（ int hash =hash(key.hashCode())），找到数组中对应位置的某一元素（table[i] = indexFor(hash,table.length)），然后通过 key 的 equals 方法在对应位置的链表中找到需要的元素的值。</p>
<h2 id="扩容机制">扩容机制</h2>
<p>。。。</p>
<hr>
<h3 id="负载因子">负载因子</h3>
<p>装填因子（Load Factor）：节点总数量 / 哈希表桶数组长度，也叫做负载因子
◼ 在JDK1.8的HashMap中，如果装填因子超过0.75，就扩容为原来的2倍</p>
<h2 id="其他问题">其他问题</h2>
<ul>
<li>
<p><strong>对象的equals相同,但是hashCode返回只不同会有什么问题?</strong></p>
<p>相同的元素放入到hash不同的桶中.容易让hashMap混乱,无法标识同一个对象,代码不稳定.</p>
</li>
<li>
<p><strong>hashCode返回值相同,但是对象的equals不同会有什么问题?</strong></p>
<p>不同的对象,放入到hash的同一个桶中. 容易让hashMap混乱,无法标识同一个对象,代码不稳定.</p>
</li>
</ul>

    <h4><a href="https://czh-dev.gitee.io/czh-blog.gitee.io/">Back to Home</a></h4>
  </div>

  <div class="span3 bs-docs-sidebar" style="position:fixed;right: 40px;top: 50px;">
    <h1>catalogue</h1>
    <ul class="nav nav-list bs-docs-sidenav">
      <div class="toc-div">
        <nav id="TableOfContents">
  <ul>
    <li><a href="#面试题">面试题</a>
      <ul>
        <li><a href="#谈一下hashmap中put是如何实现的"><strong>谈一下hashMap中put是如何实现的？</strong></a></li>
        <li><a href="#为什么重写equals必须重写hashcode方法"><strong>为什么重写equals,必须重写hashCode方法?</strong></a></li>
        <li><a href="#谈一下hashmap中什么时候需要进行扩容扩容resize又是如何实现的"><strong>谈一下hashMap中什么时候需要进行扩容，扩容resize()又是如何实现的？</strong></a></li>
        <li><a href="#为什么不直接将key作为哈希值而是与高16位做异或运算"><strong>为什么不直接将key作为哈希值而是与高16位做异或运算？</strong></a></li>
        <li><a href="#为什么是16为什么必须是2的幂如果输入值不是2的幂比如10会怎么样"><strong>为什么是16？为什么必须是2的幂？如果输入值不是2的幂比如10会怎么样？</strong></a></li>
        <li><a href="#谈一下当两个对象的hashcode相等时会怎么样"><strong>谈一下当两个对象的hashCode相等时会怎么样？</strong></a></li>
        <li><a href="#如果两个键的hashcode相同你如何获取值对象"><strong>如果两个键的hashcode相同，你如何获取值对象？</strong></a></li>
        <li><a href="#如果hashmap的大小超过了负载因子load-factor定义的容量怎么办"><strong>如果HashMap的大小超过了负载因子(load factor)定义的容量，怎么办？</strong></a></li>
        <li><a href="#请解释一下hashmap的参数loadfactor它的作用是什么"><strong>请解释一下HashMap的参数loadFactor，它的作用是什么？</strong></a></li>
        <li><a href="#传统hashmap的缺点为什么引入红黑树"><strong>传统HashMap的缺点(为什么引入红黑树？)：</strong></a></li>
      </ul>
    </li>
    <li><a href="#存储需求">存储需求</a></li>
    <li><a href="#哈希表hash-table">哈希表（Hash Table）</a>
      <ul>
        <li><a href="#哈希冲突">哈希冲突</a></li>
        <li><a href="#jdk18的哈希冲突解决方案">JDK1.8的哈希冲突解决方案</a></li>
        <li><a href="#哈希函数">哈希函数</a></li>
        <li><a href="#如何生成key的哈希值">如何生成key的哈希值</a></li>
      </ul>
    </li>
    <li><a href="#put方法源码解析">put方法源码解析</a></li>
    <li><a href="#get方法源码解析">get方法源码解析</a></li>
    <li><a href="#扩容机制">扩容机制</a>
      <ul>
        <li><a href="#负载因子">负载因子</a></li>
      </ul>
    </li>
    <li><a href="#其他问题">其他问题</a></li>
  </ul>
</nav>
      </div>
    </ul>
  </div>

</div>
<script src="https://cdn.jsdelivr.net/npm/gumshoejs@5.1.2/dist/gumshoe.min.js"></script>
<script>
  var spy = new Gumshoe('#TableOfContents a', {
    nested: true,
    nestedClass: 'active'
  });
</script>
<style>
   
  #TableOfContents li,
  #TableOfContents ul {
    list-style-type: none;
  }

  #TableOfContents ul {
    padding-left: 0px;
  }

  #TableOfContents li>a {
    display: block;
    padding: 4px 20px;
    font-size: 95%;
    color: #000000;
  }

  #TableOfContents li>a:hover,
  #TableOfContents li>a:focus {
    padding-left: 19px;
    color: #3A6bA5;
    text-decoration: none;
    background-color: transparent;
    border-left: 1px solid #3A6bA5;
  }

  #TableOfContents li.active>a,
  #TableOfContents li.active>a:hover,
  #TableOfContents li.active>a:focus {
    padding-left: 18px;
    font-weight: bold;
    color: #3A6bA5;
    background-color: transparent;
    border-left: 2px solid #3A6bA5;
  }

   
  #TableOfContents li>ul {
    padding-bottom: 10px;
  }

  #TableOfContents li li>a {
    padding-top: 1px;
    padding-bottom: 1px;
    padding-left: 30px;
    font-size: 14px;
    font-weight: normal;
  }

  #TableOfContents li li>a:hover,
  #TableOfContents li li>a:focus {
    padding-left: 29px;
  }

  #TableOfContents li li.active>a,
  #TableOfContents li li.active>a:hover,
  #TableOfContents li li.active>a:focus {
    padding-left: 28px;
    font-weight: 500;
  }

  #TableOfContents .nav-link.active+ul {
    display: block;
  }

  #TableOfContents li>ul {
    display: none;
  }

  #TableOfContents li.active>ul {
    display: inherit;
  }

  .toc-div {
    position: -webkit-sticky;
     
    position: sticky;
     
    top: 20px;
  }
</style>


        </div><footer class="container">
    <hr class="soften">
    <p>
    <a href="https://space.bilibili.com/1799809923">Love eating fried pork ribs</a> | 

&copy; 
<a href="http://jmf-portfolio.netlify.com" target="_blank">
    JM Fergeau
</a>
<span id="thisyear">2023</span>

    | My site


        | Built on <a href="//gohugo.io" target="_blank">Hugo</a>

</p>
    <p class="text-center">
        <a href="https://facebook.com">Facebook</a> 
        <a href="https://twitter.com">Twitter</a> 
        <a href="https://linkedin.com">Linkedin</a> 
        <a href="https://github.com">GitHub</a> 
        <a href="https://gitlab.com">GitLab</a>
    </p>
</footer>

</body><link rel="stylesheet" href="/czh-blog.gitee.io/css/bootstrap.css">
<link rel="stylesheet" href="/czh-blog.gitee.io/css/bootstrap-responsive.css">
<link rel="stylesheet" href="/czh-blog.gitee.io/css/style.css">

<script src="/czh-blog.gitee.io/js/jquery.js"></script>
<script src="/czh-blog.gitee.io/js/bootstrap-386.js"></script>
<script src="/czh-blog.gitee.io/js/bootstrap-transition.js"></script>
<script src="/czh-blog.gitee.io/js/bootstrap-alert.js"></script>
<script src="/czh-blog.gitee.io/js/bootstrap-modal.js"></script>
<script src="/czh-blog.gitee.io/js/bootstrap-dropdown.js"></script>
<script src="/czh-blog.gitee.io/js/bootstrap-scrollspy.js"></script>
<script src="/czh-blog.gitee.io/js/bootstrap-tab.js"></script>
<script src="/czh-blog.gitee.io/js/bootstrap-tooltip.js"></script>
<script src="/czh-blog.gitee.io/js/bootstrap-popover.js"></script>
<script src="/czh-blog.gitee.io/js/bootstrap-button.js"></script>
<script src="/czh-blog.gitee.io/js/bootstrap-collapse.js"></script>
<script src="/czh-blog.gitee.io/js/bootstrap-carousel.js"></script>
<script src="/czh-blog.gitee.io/js/bootstrap-typeahead.js"></script>
<script src="/czh-blog.gitee.io/js/bootstrap-affix.js"></script>
<script>
    _386 = { 
        fastLoad: false ,
        onePass: false , 
        speedFactor: 1 
    };

    
    function ThisYear() {
        document.getElementById('thisyear').innerHTML = new Date().getFullYear();
    };
</script>
</html>
